package 动态规划专项训练.动态规划训练2;


/**265.粉刷房子II
 * (leetcode会员)
 * @author zx
 * @create 2022-03-31 18:56
 */
public class  Num265 {
    public int minCost(int[][] A) {
        if(A.length == 0){
            return 0;
        }
        int n = A.length;
        int k = A[0].length;
        int[][] f = new int[n + 1][k];
        int min1,min2;
        int j1 = 0,j2 = 0;//j1,j2代表最小值和次小值的下标
        for(int j = 0;j < k;j++){
            f[0][j] = 0;
        }
        for(int i = 1;i <= n;i++){
            //计算min1,min2(求最小值和次小值)
            min1 = min2 = Integer.MAX_VALUE;
            //min1 = f[i - 1][j1]
            //min2 = f[i - 1][j2]
            for(int j = 0;j < k;j++){
                if(f[i - 1][j] < min1){
                    //比原来的最小值都小,则把原来的最小值放到次小值里
                    //然后再把现在的值赋给最小
                    min2 = min1;
                    j2 = j1;
                    min1 = f[i - 1][j];
                    j1 = j;
                }else{
                    //比最小值大,比次小值小
                    if(f[i - 1][j] < min2){
                        min2 = f[i - 1][j];
                        j2 = j;
                    }
                }
            }
            for(int j = 0;j < k;j++){
                if(j != j1){
                    f[i][j] = f[i - 1][j1] + A[i - 1][j];
                }else{
                    //j == j1(正好是那个最小值)
                    f[i][j] = f[i - 1][j2] + A[i - 1][j];
                }
            }
        }
        int res = Integer.MAX_VALUE;
        for(int j = 0;j < k;j++){
            res = Math.min(res,f[n][j]);
        }
        return res;
    }
}
